//
// Created by francklinson on 2021/9/20 AT 21:17.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>

using namespace std;

class Solution {
public:
    int findNumberOfLIS(vector<int> &nums) {
        // dp[i]：以nums[i]为结尾的最长递增子序列的长度
        int n = (int) nums.size();
        vector<int> dp(n, 1);
        vector<int> count(n, 1);  // 最长的有几个
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    if (dp[j] >= dp[i]) {
                        dp[i] = 1 + dp[j];
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
            }
        }
        int longest = *max_element(dp.begin(), dp.end());
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (dp[i] == longest)
                ans += count[i];
        }
        return ans;
    }
};

int main() {
    vector<int> nums{1, 3, 5, 4, 7};
    Solution solution;
    cout << solution.findNumberOfLIS(nums) << endl;
    return 0;
}

